/*
https://leetcode.cn/problems/delete-operation-for-two-strings/submissions/567947871/
583. 两个字符串的删除操作
完成日期：2024/9/6
线性dp
*/

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
     vector<vector<int>> dp(n1+1,vector<int>(n2+1, 0));
        for (int i=1;i<=n1;++i) {
            for (int j=1;j<=n2;++j) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        //两个字符串的长度分别减去最长公共子串的长度即为最少删除次数
        return n1+n2-2*dp[n1][n2];
    }

};